/*
 * @lc app=leetcode.cn id=28 lang=java
 *
 * [28] 实现 strStr()
 */

// @lc code=start
class Solution {
    public int strStr(String haystack, String needle) {
        if(needle==null||needle.equals("")) return 0;
        return KMP.search(haystack, needle);

    }

    static class KMP {
        
        String s;
        int[] next;
    
        KMP(String s) {
            this.s = s;
            next = new int[s.length() + 1];
            setNext();
        }
    
        void setNext() {
            int i = 0, j = -1;
            next[0] = -1;
            while (i < next.length) {
                if (j == -1 || s.charAt(i) == s.charAt(j)) {
                    i++;
                    j++;
                    if(i==s.length()) break; 
                    if (s.charAt(i) != s.charAt(j)) {
                        next[i] = j;
                    } else {
                        next[i] = next[j];
                    }
                } else {
                    j = next[j];
                }
            }
        }
    
        int search(String txt) {
            int i = 0, j = 0;
            // 省略错误检查
            while (i < txt.length() && j < s.length()) {
                if(j==-1||txt.charAt(i)==s.charAt(j)){
                    i++;j++;
                }
                else{
                    j=next[j];
                }
            }
            if(j==s.length()){
                return i-j;
            }
    
            return -1;
        }
    
        static int search(String txt,String pat){
            return new KMP(pat).search(txt);
        }
    
    
    }
}
// @lc code=end

/**
 * 我的解：Your runtime beats 5.04 % of java submissions Your memory usage beats
 * 12.61 % of java submissions (39 MB)
 * 
 * 分析之后其实就是更蠢的暴力法
 * 
 */

/**
 * 点：尤其手写，先取长度（这在java很快），再多依据长度算
 */


